#define _CRT_SECURE_NO_WARNINGS 1

#include <cstring>
class Solution {
public:
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        int dp[1010][1010];
        memset(dp, 0, 4);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= V; j++)
            {
                if (j >= vw[i - 1][0])
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                else
                    dp[i][j] = dp[i - 1][j];
                cout << dp[i][j] << ' ';
            }
            cout << endl;
        }
        return dp[n][V];
    }
};